With the increased prevalence of electronic imaging devices and the Internet, billions of digital images have become publically available and searchable online. Indexing such a huge amount of data to enable users to quickly find desired images is a massive and difficult task. For example, many images are posted without an accurate description or tagging, making it difficult to index such images using typical keyword techniques. Consequently, when a user desires to locate a complex image having particular features, conventional text-based search engines that rely on short text queries are often unable to locate desired images in a timely and efficient manner.
Additionally, while sketch-based searching of image databases has been intensively studied, little progress has been made in developing practical large-scale sketch-based search techniques. Attempts at constructing large-scale sketch-based search system have been unsuccessful for various reasons. For example, some proposed techniques lack effective edge representation and have been unable to quickly and accurately compare an input sketch with indexed images. Other proposed techniques have been unable to achieve a scalable index solution, resulting in indexes of unmanageable size or complexity when applied to many millions of images.